package quwei;
//哈夫曼编码
import java.util.Scanner;

/*结点类*/
class HNodeType{
    double weight;                           //权值
    int parent;                              //父亲结点
    int lchild;                              //左孩子
    int rchild;                              //右孩子
    char value;                              //该节点表示的字符             
}

/*编码类*/
class HCodeType{
    final int MAXBIT=100;
    int[] bit=new int[MAXBIT];               //存储编码的数组
    int start;                               //编码开始下标
}

public class Test2_6 {

    static final int MAXVALUE=10000;

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        System.out.println("请输入结点个数：");
        int n=scanner.nextInt();

        HCodeType[] HuffCode=new HCodeType[n];                                        //定义一个编码类数组                          
        HNodeType[] HuffNode=new HNodeType[2*n-1];                                    //定义一个结点类数组

        HuffmanTree(HuffNode,n);                                                      //构造哈夫曼树
        HuffmanCode(HuffNode,HuffCode,n);                                             //哈夫曼树编码

        //输出已保存好的哈夫曼编码
        for(int i=0;i<n;i++) {
            System.out.print(HuffNode[i].value+": Huffman code is: ");
            for(int j=HuffCode[i].start+1;j<n;j++)
                System.out.print(HuffCode[i].bit[j]);
            System.out.println();
        }
        scanner.close();
    }

    /*构造哈夫曼树*/
    public static void HuffmanTree(HNodeType[] HuffNode,int n) {
        Scanner scanner=new Scanner(System.in);
        int i,j,x1,x2;
        double m1,m2;
        for(i=0;i<2*n-1;i++) {                                                        //初始化存放哈夫曼树数组中的结点
            HuffNode[i]=new HNodeType();                                              
            HuffNode[i].weight=0;
            HuffNode[i].parent=-1;
            HuffNode[i].lchild=-1;
            HuffNode[i].rchild=-1;
        }

        for(i=0;i<n;i++) {                                                            //输入n个叶子结点的权值
            System.out.println("请输入第"+(i+1)+"个结点的字符和权值：");
            String str=scanner.next();
            HuffNode[i].value=str.charAt(0);
            HuffNode[i].weight=scanner.nextDouble();
        }

        for(i=0;i<n-1;i++) {                                                          //执行n-1次合并

            m1=m2=MAXVALUE;                                                           //存放无父节点且权值最小的两个结点的权值
            x1=x2=-1;                                                                 //权值最小的两个结点在数组中的下标
            for(j=0;j<n+i;j++) {                                                      //找出无父节点且权值最小的两个结点，合并成一颗二叉树
                if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1) {
                    m2=m1;
                    x2=x1;
                    m1=HuffNode[j].weight;
                    x1=j;
                }
                else if(HuffNode[j].weight<m2&&HuffNode[j].parent==-1) {
                    m2=HuffNode[j].weight;
                    x2=j;
                }
            }

            //设置找到的两个结点的父节点的信息
            HuffNode[x1].parent=n+i;                                                   
            HuffNode[x2].parent=n+i;
            HuffNode[n+i].lchild=x1;                                                   //新结点的左孩子节点是权值最小的结点的下标
            HuffNode[n+i].rchild=x2;                                                   //新结点的右孩子节点是权值次小的结点的下标
            HuffNode[n+i].weight=m1+m2;                                                //权值是两个最小权值之和
            System.out.printf("x1和x2的权值分别是：%.2f %.2f",m1,m2);
            System.out.println();
        }
    }

    /*哈夫曼树编码*/
    public static void HuffmanCode(HNodeType[] HuffNode,HCodeType[] HuffCode,int n) {
        HCodeType cd=new HCodeType();                                                 //定义临时变量存放求解编码时的信息
        int c;                                                                        //表示结点下标变量
        int p;                                                                        //表示当前结点的父节点
        for(int i=0;i<n;i++) {                                                        //共有n个叶子结点
            HuffCode[i]=new HCodeType();
            cd.start=n-1;                                                             //从后往前存放
            c=i;
            p=HuffNode[c].parent;
            while(p!=-1) {                                                            //自底向上遍历，只要存在父节点就继续向上走
                if(HuffNode[p].lchild==c) {                                           //若当前结点是p的左孩子则编码0
                    cd.bit[cd.start]=0;
                }
                else {                                                                //右孩子则编码1
                    cd.bit[cd.start]=1;
                }
                cd.start--;                                                           //求编码的下一位
                c=p;                                                                  //变量上移，准备下一次循环
                p=HuffNode[c].parent;
            }

            //把叶子结点的编码信息从临时编码cd中复制到编码数组中
            for(int j=cd.start+1;j<n;j++) 
                HuffCode[i].bit[j]=cd.bit[j];
            HuffCode[i].start=cd.start;                                                //指向编码开始的前一位
        }
    }
}
